package jianzhiOffer;

/**
 * 42. 连续子数组的最大和
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * <p>
 * 要求时间复杂度为O(n)。
 *
 * @author 司松坡
 * @createTime 2023年04月26日
 */
public class JIan42 {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i-1] > 0) {
                nums[i] = nums[i - 1] + nums[i];
            }
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}
